#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_TEMPO 1000000.0

int main (int argc, char **argv)
{
	int i;
	char heuristica = '2';

	if (argc != 3)
	{
		printf("Usage: trab1 <filtered.txt.2> <solution>\n\n");
		return 0;
	}


	FILE *inFile = fopen(argv[1],"r");
	if(inFile == NULL)
	{
		printf("Erro ao abrir o arquivo.\n");
		return 1;
	}

	FILE *outFile = fopen(argv[2],"w");
	if(inFile == NULL)
	{
		printf("Erro ao abrir o arquivo.\n");
		return 1;
	}

    // N - numero de pessoas
	int N = 0;
	fscanf(inFile, "%d", &N);
	printf("N = %d\n", N);

    // K - numero de tipos de veiculos
	int K = 0;
	fscanf(inFile, "%d", &K);
	printf("K = %d\n", K);

    // v - numero de veiculos de cada tipo
	int *v;
	v = (int*) malloc (K * sizeof(int));

	int aux;
	for (aux = 0 ; aux < K ; aux++)
	{
		fscanf(inFile,"%d", &v[aux]);
		printf("v[%d] = %d\n", aux, v[aux]);
	}

	int *vcap;
	vcap = (int*) malloc (K * sizeof(int));

	for (aux = 0 ; aux < K ; aux++)
	{
		fscanf(inFile,"%d", &vcap[aux]);
		printf("vcap[%d] = %d\n", aux, vcap[aux]);
	}

	double maxtt = 0.0;
	fscanf(inFile, "%lf", &maxtt);
	printf("maxtt = %.2lf\n", maxtt);

	double st = 0.0;
	fscanf(inFile, "%lf", &st);
	printf("st = %.2lf\n", st);

	double **adjMat;
	adjMat = (double**) malloc ((N+2) * sizeof(double*));
	for (aux = 0 ; aux < (N+2) ; aux++)
	{
		adjMat[aux] = (double*) malloc ((N+2) * sizeof(double));
	}

	int aux2;
	for (aux = 0 ; aux < (N+2) ; aux++)
	{
		for (aux2 = 0 ; aux2 < (N+2) ; aux2++)
		{
			fscanf(inFile, "%lf", &adjMat[aux][aux2]);
			if (adjMat[aux][aux2] == 0.0)
			{
				adjMat[aux][aux2] = MAX_TEMPO;
			}
			printf("%.2lf ", adjMat[aux][aux2]);
		}
		printf("\n");
	}
	printf("\n");

	double *alpha;
	alpha = (double*) malloc (K * sizeof(double));

	for (aux = 0 ; aux < K ; aux++)
	{
		fscanf(inFile,"%lf", &alpha[aux]);
		printf("alpha[%d] = %.2lf\n", aux, alpha[aux]);
	}

	double *f;
	f = (double*) malloc (K * sizeof(double));

	for (aux = 0 ; aux < K ; aux++)
	{
		fscanf(inFile,"%lf", &f[aux]);
		printf("f[%d] = %.2lf\n", aux, f[aux]);
	}

	fclose(inFile);

	int *visitados;
	visitados = (int*) malloc (N * sizeof(int));
	for (i = 0 ; i < N ; i++)
	{
		visitados[i] = 0;
	}
	
	printf("\n");

	int todosVisitados = 0;
	int numeroNosVisitados = 0;
	double custoTotal = 0.0;

	clock_t begin, end;
	double time_spent;

	begin = clock();

	//Loop principal. Irá rodar enquanto existirem pessoas a serem carregadas ou acabaram os carros
	while(!todosVisitados)
	{
		//Descobrir o veículo mais adequado para uso. A heurística utiliza o maior veículo o possível
		int veiculo = 0;
		double indice = (f[veiculo] * alpha[veiculo])/vcap[veiculo];
		if (heuristica == '1')
		{
			for (aux = 0 ; aux < K ; aux++)
			{
				if ((v[aux] > 0) && (vcap[veiculo] < vcap[aux]))
				{
					veiculo = aux;
				}
			}	
		}
		else if (heuristica == '2')
		{
			for (aux = 0 ; aux < K ; aux++)
			{
				double indiceAux = (f[aux] * alpha[aux])/vcap[aux];
				if ((v[aux] > 0) && (indice < indiceAux))
				{
					veiculo = aux;
				}
			}	
		}
		else
		{
			printf("Erro na seleção da heurística.\n");
			return 1;
		}

		fprintf(outFile, "#Veiculo tipo %d:\n0", veiculo);
		printf("#Veiculo tipo %d:\n0", veiculo);

		//Utiliza o veiculo selecionado
		v[veiculo]--;

		//Inicializa o percurso
		double custo = f[veiculo];
		double coefVeiculo = alpha[veiculo];
		double tempoRestante = maxtt;
		int lotacao = 0;
		int localizacaoAtual = 0;
		int veiculoCheio = 0;
		int tempoInsuficiente = 0;

		//A heurística dita que sejam visitados os nós mais próximos do nó atual primeiro
		while(!veiculoCheio && !tempoInsuficiente && !todosVisitados)
		{
			//Se ainda há nós para visitar
			if (numeroNosVisitados != N)
			{
				//Encontrar o nó mais próximo e não visitado do nó atual
				int proximoNo = -1;
				for (aux = 1 ; aux < N+1 ; aux++)
				{
					if (visitados[aux] != 1)
					{
						proximoNo = aux;
						break;
					}
				}
				
				for (aux = 1 ; aux < N+1 ; aux++)
				{
					//Encontra nó mais próximo que não seja o próprio nó e nós que já tenham sido visitados
					if ((adjMat[localizacaoAtual][aux] < adjMat[localizacaoAtual][proximoNo]) && (visitados[aux] != 1))
					{
						proximoNo = aux;
					}
				}

				//Testar se o veículo ainda pode visitar o próximo nó ou se deve ir até o destino
				if (tempoRestante <= (adjMat[localizacaoAtual][proximoNo] + adjMat[proximoNo][N+1] + st))
				{
					//Não há mais tempo de visitar o próximo nó
					tempoInsuficiente = 1;
					custo += (adjMat[localizacaoAtual][N+1] * coefVeiculo + st * coefVeiculo);
					tempoRestante -= (adjMat[localizacaoAtual][N+1] + st);
					fprintf(outFile, "-D: %.2lf\n\n", (maxtt - tempoRestante));
					printf("-D: %.2lf\n\n", (maxtt - tempoRestante));
				}
				else
				{
					//Se o veiculo está lotado ou ainda pode buscar mais uma pessoa
					if (lotacao != vcap[veiculo])
					{
						//Visitar o próximo nó e buscar a pessoa
						custo += (adjMat[localizacaoAtual][proximoNo] * coefVeiculo + st * coefVeiculo);
						visitados[proximoNo] = 1;
						numeroNosVisitados++;
						lotacao++;
						tempoRestante -= (adjMat[localizacaoAtual][proximoNo] + st);
						localizacaoAtual = proximoNo;
						fprintf(outFile, "-%d", localizacaoAtual);
						printf("-%d", localizacaoAtual);
					}
					else
					{
						//Veículo já está cheio e deve ir direto ao ponto final
						veiculoCheio = 1;
						custo += (adjMat[localizacaoAtual][N+1] * coefVeiculo + st * coefVeiculo);
						tempoRestante -= (adjMat[localizacaoAtual][N+1] + st);
						fprintf(outFile, "-D: %.2lf\n\n", (maxtt - tempoRestante));
						printf("-D: %.2lf\n\n", (maxtt - tempoRestante));
					}
				}
			}
			else
			{
				//Todos os nós já foram visitados
				todosVisitados = 1;
				custo += (adjMat[localizacaoAtual][N+1] * coefVeiculo + st * coefVeiculo);
				tempoRestante -= (adjMat[localizacaoAtual][N+1] + st);
				fprintf(outFile, "-D: %.2lf\n\n", (maxtt - tempoRestante));
				printf("-D: %.2lf\n\n", (maxtt - tempoRestante));
			}
		}

		custoTotal += custo;
	}

	end = clock();
	time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

	fprintf(outFile, "#Sol: %.2lf\n", custoTotal);
	printf("#Sol: %.2lf\n", custoTotal);

	fprintf(outFile, "#Tempo: %.3lf\n", time_spent);
	printf("#Tempo: %.3lf\n", time_spent);

	fclose(outFile);

	return 0;
}